//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
//
// Related Topics 回溯 👍 1424 👎 0


package leetcode.editor.cn;

// [77]组合


import java.util.ArrayList;
import java.util.List;

public class Combinations_77 {
    public static void main(String[] args) {
        Solution solution = new Combinations_77().new Solution();
        System.out.println(solution.combine(5, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int N;
        int K;
        List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> combine(int n, int k) {
            if (n < k) {
                return null;
            }
            N = n;
            K = k;
            process(1, 0, new ArrayList<>());
            return list;
        }

        public void process(int i, int size, ArrayList<Integer> path) {
            if (size == K) {
                list.add(path);
                return;
            }
            if (i <= N) {
                ArrayList<Integer> clone = (ArrayList<Integer>) path.clone();
                clone.add(i);
                process(i + 1, size, path);
                process(i + 1, size + 1, clone);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}